//输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 
//
// 
//
// 示例 1: 
//
// 输入: [10,2]
//输出: "102" 
//
// 示例 2: 
//
// 输入: [3,30,34,5,9]
//输出: "3033459" 
//
// 
//
// 提示: 
//
// 
// 0 < nums.length <= 100 
// 
//
// 说明: 
//
// 
// 输出结果可能非常大，所以你需要返回一个字符串而不是整数 
// 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 
// 
//
// Related Topics 贪心 字符串 排序 👍 664 👎 0


package leetcode.editor.cn;

import java.util.HashMap;

class 把数组排成最小的数{
    public static void main(String[] args) {
        Solution solution = new 把数组排成最小的数().new Solution();
        
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int[] nums;
    String[] strs;
    public String minNumber(int[] nums) {
        this.nums = nums;
        strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(0,strs.length - 1);
        StringBuilder res = new StringBuilder();
        for (String s : strs){
            res.append(s);
        }
        return res.toString();
    }
    
    void quickSort(int left,int right){
        if (left >= right) return;
        int l = left,r = right;
        while (l < r){
            while (l < r && (strs[l] + strs[r]).compareTo(strs[r] + strs[l]) <= 0) l++;
            swap(l,r);
            while (l < r && (strs[l] + strs[r]).compareTo(strs[r] + strs[l]) <= 0) r--;
            swap(l,r);
        }
        quickSort(left,l-1);
        quickSort(l+1,right);
    }
    
    void swap(int a,int b){
        String tmp = strs[a];
        strs[a] = strs[b];
        strs[b]= tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
